package _dp_base;

/**
 * 646. 最长数对链
 */
public class No646 {
    private int[][] pairs;
    private int[] cache;

    /**
     * 1. 递归
     */
    public int findLongestChain1(int[][] pairs) {
        this.pairs = pairs;
        int n = pairs.length;
        cache = new int[n];

        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.max(dfs(i), answer);
        }
        return answer;
    }

    private int dfs(int i) {
        if (cache[i] != 0) return cache[i];
        int curLen = 1;
        for (int j = 0; j < pairs.length; j++) {
            if (pairs[j][1] < pairs[i][0]) {
                int preMaxLen = dfs(j);
                if (preMaxLen + 1 > curLen) curLen = preMaxLen + 1;
            }
        }
        return cache[i] = curLen;
    }
}
